The node-edge weighted 2-edge connected subgraph problem: Linear relaxation, facets and separation

Let G=(V,E) be a undirected k-edge connected graph with weights c_e on edges and w_v on nodes. The minimum 2-edge connected subgraph problem, 2ECSP for short, is to find a 2-edge connected subgraph of G, of minimum total weight. The 2ECSP generalizes the well-known Steiner 2-edge connected subgraph problem. In this paper we study the convex hull of the incidence vectors corresponding to feasible solutions of 2ECSP. First, a natural integer programming formulation is given and it is shown that its linear relaxation is not sufficient to describe the polytope associated with 2ECSP even when G is series-parallel. Then, we introduce two families of new valid inequalities and we give sufficient conditions for them to be facet-defining. Later, we concentrate on the separation problem. We find polynomial time algorithms to solve the separation of important subclasses of the introduced inequalities, concluding that the separation of the new inequalities, when G is series-parallel, is polynomially solvable.     

Partitioning series-parallel multigraphs into ν *-excluding edge covers

We prove that, for any given vertex ν* in a series-parallel graph G, its edge set can be partitioned into κ = min{κ′(G) + 1, δ(G)} subsets such that each subset covers all the vertices of G possibly except for ν*, where δ(G) is the minimum degree of G and κ′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

纵横扩张的优化

得到了最小折数纵横扩张的判别准则．针对4-正则图的平面嵌入的纵横扩张的特殊性，给出了它的最小折数纵横扩张判别准则．     

极紫外望远镜各通道夹角的测量

极紫外望远镜是由四个单通道的望远镜捆绑在一起,以便同时对太阳的相同部分观测,由于受地面装调以及发射过程中的影响,无法保证四个通道光轴严格平行,必然带来观测位置上的误差。只要测出各通道之间的光轴夹角,便可在像面上采取适当的处理方法,以便减小这种误差,但这一夹角的测量精度必须控制在0.1″内。为达到如此高的精度,采用了太阳局部边缘探测的方法,很好地解决了这一问题。     

The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Energy transfer between the flavin chromophores of electron-transferring flavoprotein fromMegasphaera elsdenii as inferred from time-resolved red-edge and blue-edge fluorescence spectroscopy

Both a mode-locked argon-ion laser and synchrotron radiation were used as excitation sources to obtain time-resolved polarized fluorescence of the two FAD cofactors in electron transferring flavoprotein fromMegasphaera elsdenii. Red-edge excited and blue-edge detected fluorescence anisotropy decay curves did not contain a fast relaxation process which was observed upon mainband excitation and detection. This relaxation was assigned to homo-energy transfer between the two FAD cofactors. Failure of energy transfer as observed with edge spectroscopy on this protein excludes restricted reorientational motion of the flavins as a possible mechanism of depolarization. From the global analysis of the fluorescence anisotropy decay surface obtained at multiple excitation and detection wavelengths, the distance between and the relative orientation of the flavins could be estimated. The methodology described has general applicability in other multichromophoric biopolymers and has the potential to acquire accurate geometrical parameters in these systems.     

单循环赛赛程安排的一个图论方法

利用图论的边着色理论建立了一个赛程安排的数学模型 .首先建立 n支球队与完全图 Kn的 n个顶点间的一一对应 ,把球队 Ai和 Aj间的比赛关系抽象成 Kn的顶点 i和 j间的边 ( i,j) .然后分别构造出了图K2 m- 1和 K2 m的正常 2 m-1边着色 .从而给出了各球队每两场比赛间得到的休整时间最均等 ,休整的间隔场次数达到上限值 n2 的一个赛程安排方案     

Roughness reduction in submicron waveguides by low-molecular weight development

Roughness reduction of a submicron waveguide profile in chemically amplified negative resist is here performed by proper selection of an alkali-based developer, taking into account that its smaller molecules lead to smoother resist surface by altering the developing mechanism of aggregate extraction performed with standard quaternary ammonium hydroxide. Roughness is then analyzed by means of classical Atomic Force Microscope inspection; furthermore, a non-invasive line edge roughness analysis approach based on top-down scanning electron microscope acquisition gives comparable results, in terms of standard deviation and molecular aggregate periodicity.     

自然地面背景下红外目标检测算法

为了快速准确地检测出以地面物体为背景的红外序列图像中的目标,结合小波变换的特点及其应用于图像边缘检测的优点,提出了一种基于小波技术的图像预处理算法。该方法利用图像边缘在目标识别中的重要作用,讨论了基于小波变换的图像边缘检测方法,并结合地面背景红外图像自身的特点,大大地提高了单帧的检测概率。     

一类非线性方程解的存在和唯一性及在图像中的应用

本文我们给出一个修正的非线性扩散方程模型，与Cotte Lions和Morel的模型相比该模型有许多实质上的优点。主要的想法是把原来去噪声部分：卷积Gauss过程替代为解一个有界区域上的线性抛物方程问题，因此避开了对初始数值如何全平面延拓的问题。我们从数学上的证明该问题解的存在性和适定性，同时给出对矩形域情况的解的级数形式。最后我们给基于本模型的数值计算差分模型，并且给出几个具体图像在该模型下处理结果。